Jupyter at Bryn Mawr College
Public notebooks: /services/public/dblank / CS206 Data Structures / 2016-Spring / Notebooks

1. Data Structure Review

  • Spring 2016, Blank
  • Bryn Mawr College
  • "Data Structures: Abstraction and Design Using Java", by Koffman & Wolfgang

1.1 Data Structures

  • List interface (page 61, 124)
  • LinkedList (page 88)
  • Double-Linked List (page 99)
  • Circular List (page 99)
  • Node (page 90)
  • ArrayList (page 62)
  • Queue (page 195)
  • Stack (page 149)
  • Double-ended Queue ("Deque", pronounced "deck") (page 217)
  • Tree (page 295)
  • Binary Tree (page 298)
  • Binary Search Tree (page 300)
  • Set (page 362)
  • Map (page 367)
  • Hashes, Hash Table (page 372)
    • Open addressing (page 374)
    • Chaining (page 379)
    • Collision (page 377)
    • Linear Probe (page 374)
    • Quadratic Probe (page 378)
  • Navigable Set and Map (page 408)
  • Self-Balancing Search Trees (page 471)
    • Balance and Rotations (page 472)
    • AVL Tree (page 477)
    • Red-Black Tree (page 490)
  • Graph (page 541)
    • Directed (page 543)
    • Undirected (page 543)
    • Path, Cycles, (page 544)
    • Breadth-First Search (page 560)
    • Depth-First Search (page 566)
    • Dijkstra's Algorithm (page 582)
    • Minimum Spanning Tree (page 584)

1.2 Sorting

  • Bubble Sort (page 428)
  • Double Trouble (similar to Selection Sort, page 426)
  • Quicksort (page 451)

1.3 Terms and Concepts

  • ADT (page 2)
  • JVM (page 2)
  • Java API (page 2)
  • Interface (page 3)
  • implements (page 6)
  • instantiate and interface (page 7)
  • Object-Oriented Programming )page 8)
  • superclass and subclass (page 9)
  • this (page 10)
  • data fields (page 11)
  • super(...) (page 11)
  • no-parameter constructor (page 12)
  • is-a vs. has-a (page 13)
  • polymorphism (page 19)
  • abstract classes (page 22)
  • multiple interfaces (page 26)
  • primitive type (page 602)
  • wrappers for primitive types (page 24)
  • casting (page 27)
  • toString() (page 28)
  • instanceof (page 31)
  • private/protected/public (page 44)
  • hierarchy (page 46)
  • factory method (page 52)
  • generics, generic collection (page 66)
  • Big-O notation (page 80)
  • enhanced for statement (Type var: collection) (page 110)
  • Collection interface (page 121)
  • generic types (page 127)
  • recursion (page 243)
  • stack overflow (page 253)
  • recursion vs. iteration (page 255)
  • recursive gcd (page 254)
  • linear and binary search (page 260)
  • breadth-first search, binary tree (page 357)

1.4 Errors and Exception Handling

  • Null Pointer (page 35)
  • Array Index Out of Bounds ((page 35)
  • try/catch (page 39)
  • throw (page 41)

1.5 Bonus Terms

  • iterator (page 105)
  • ListIterator - page (page 108)
  • inner classes: static and nonstatic (page 120)
  • testing (page 130)
  • testing: preconditions/postconditions (page 137)
  • pseudorandom numbers (page 233)
  • Huffman Tree (page 299)
  • Heap (page 332)
  • Priority Queue (page 332)
  • 2-3 Trees (page 503)
  • B-Trees (page 510)
  • B+Tree (page 520)
  • 2-3-4 Trees (page 520)
  • Skip List (page 525)